1. Field of the Invention
The present invention relates to multi-node communication networks. More particularly, the invention concerns a process, apparatus, and article of manufacture useful for resolving conflicts between different nodes for access to the same requested node.
2. Description of the Related Art
In today's market, engineers are developing more and more powerful automated electronic machines and subcomponents, such as personal computers, printers, display monitors, printed circuit boards, and the like. As the power of these devices increases, so must their ability to communicate with each other. A device's computation power is diminished if it cannot communicate quickly and efficiently with other devices.
Inter-device conflicts are one type of problem that frustrates efficient communications. This occurs when a requesting device cannot communicate with a target device because the target device is already communicating with another device. Communication conflicts most often arise in multi-node networks, since these networks include many different intercommunicating nodes, which frequently make overlapping communication requests.
In one common scenario, the conflict occurs because the communication path to the target device is busy, irrespective of whether the target device itself is busy. This situation often arises where multiple devices share a common bus. If the bus is busy, a requesting device cannot access the target device, irrespective of whether the target device itself is busy.
Engineers have developed a number of different techniques for resolving conflicts in various single-communications-path systems. One such technique is called "exponential backoff". With exponential backoff, a node that experiences a communications conflict waits for a predetermined time, and then re-attempts the communications. For each unsuccessful attempt, the node multiplicatively increases the wait, e.g., doubling the previous wait. Thus, with repeated unsuccessful attempts, the node's wait increases exponentially. During the wait times, the node sits idle or performs self-contained processing.
Although exponential backoff may satisfy many applications, it may not be entirely adequate for certain other uses. One potential drawback may manifest itself when two requesting nodes are seeking access to the same target node. If the nodes both commence the same exponential backoff routine simultaneously, the nodes' waiting periods and retry attempts will occur at the same times. Thus, both nodes will be frustrated in their attempts to communicate with the target node. Furthermore, the efficiency of these nodes is sharply reduced, since both nodes spend a significant time unsuccessfully attempting to resolve a simple conflict.
Another conflict resolution technique for single-communication-path systems is called "random backoff". With random backoff, a node that experiences a communications conflict waits for a randomly determined time, and then reattempts the communications. For each unsuccessful attempt, the node waits for a different randomly computed period of time before retrying. During the wait times, the node sits idle or performs self-contained processing.
Random backoff provides a useful conflict resolution tool that has many different applications. However, in certain high traffic networks, a requesting node may waste a substantial amount of time attempting to communicate with a target mode that is busy for along period of time. The delay is further compounded by the inefficiencies of "context switching", as the requesting node repeatedly switches between some background application and its attempts to communicate with the target node. In other cases, the requesting node may be frustrated if, while the requesting node backs off and waits, the target node may free up but quickly re-engage in commnmications with another node. Furthermore, occasions can arise when two nodes generate a sufficiently similar random number that they wait for the same period, and then concurrently reattempt communications, thus conflicting with each other again.
With both exponential backoff and random backoff approaches, the frustrated requesting nodes' efficiency is reduced while they wait for a communications path with the target node to open up. Not only are the requesting nodes prevented from communicating with the target node, but the occupied common communications path prevents them from communicating with any other nodes for which communication jobs may be pending. This wastes channel bandwidth by repeatedly attempting to send the message, and also incurs significant context switching overhead.